import java.util.LinkedList;

public class SquareRemover {
	public final static int TIME_LIMIT = BackupAdmin.class.getName().length() + 9000; // 29500

	public final static int MOD = Integer.MAX_VALUE;
	public final static int MUL = 48271;
	public final static int MAX_POW = 6;
	public static final int UP = 0, RIGHT = 1, DOWN = 2, LEFT = 3;
	public final static int[] dx = new int[] { -1, 0, 1, 0 };
	public final static int[] dy = new int[] { 0, 1, 0, -1 };

	int[][] map = null;
	int width = 0, height = 0, nrColors = 0;

	int[] colorVals = new int[40000];
	int colInd = 0;

	int[] cres = new int[30000];
	int cInd = 0, cScore = 0;

	MyLinkedList toCheckList = new MyLinkedList();

	private int maxI1, maxJ1, maxCol1, maxI2, maxJ2, maxCol2;
	private int nextIndStop = 0;
	private State bestState = null;

	public int[] playIt(int colors, String[] board, int startSeed) {
		init(colors, board, startSeed);

		System.out.println("wd = " + width + ", ht = " + height);

		for(int step = 0; step < 100; step++) {
			nextIndStop = 200 * (step + 1);
			process(3);
			loadState(bestState);
			bestState = null;
		}

		while(cInd < cres.length) {
			identifySimpleBestSquares();
			createCell(maxI1, maxJ1, maxCol1);
		}
		System.out.println("final score = " + cScore);

		return cres;
	}

	void process(int nr) {
		if(nr > 0) {
			identifyBestSquares();
			State state = saveState();
			int mi2 = maxI2, mj2 = maxJ2, mc2 = maxCol2;
			createCell(maxI1, maxJ1, maxCol1);
			process(nr - 1);
			if(mi2 > 0 && mj2 > 0) {
				loadState(state);
				createCell(mi2, mj2, mc2);
				process(nr - 1);
			}
		} else {
			while(cInd < nextIndStop) {
				identifySimpleBestSquares();
				createCell(maxI1, maxJ1, maxCol1);
			}
			if(bestState == null
			    || (bestState.step > cInd && bestState.score <= cScore)
			    || (bestState.step >= cInd && bestState.score < cScore)) {
				bestState = saveState();
			}
		}
	}

	State saveState() {
		State state = new State();
		state.cMap = mapCopy();
		state.step = cInd;
		state.genStep = colInd;
		state.score = cScore;
		state.sRes = new int[cInd];
		System.arraycopy(cres, 0, state.sRes, 0, cInd);
		return state;
	}

	void loadState(State state) {
		this.map = state.cMap;
		this.cInd = state.step;
		this.colInd = state.genStep;
		this.cScore = state.score;
		System.arraycopy(state.sRes, 0, cres, 0, cInd);
	}

	void identifySimpleBestSquares() {
		// identify the map power and the best squares
		int maxPow = 0;
		for(int i = 1; i < height; i++) {
			for(int j = 1; j < width; j++) {
				int pow = getPower(i, j);
				if(pow / nrColors > maxPow / nrColors) {
					maxPow = pow;
					maxI1 = i;
					maxJ1 = j;
					maxCol1 = pow % nrColors;
				}
			}
		}
	}

	void identifyBestSquares() {
		// identify the map power and the best squares
		int maxPow = 0;
		for(int i = 1; i < height; i++) {
			for(int j = 1; j < width; j++) {
				int pow = getPower(i, j);
				if(pow / nrColors > maxPow / nrColors) {
					maxPow = pow;
					maxI2 = maxI1;
					maxJ2 = maxJ1;
					maxCol2 = maxCol1;
					maxI1 = i;
					maxJ1 = j;
					maxCol1 = pow % nrColors;
				} else if(pow / nrColors == maxPow / nrColors && maxI2 == -1) {
					maxI2 = i;
					maxJ2 = j;
					maxCol2 = pow % nrColors;
				}
			}
		}
	}

	// should switch until the cell at x-1, y-1, x, y is formed
	void createCell(int x, int y, int col) {
		for(int xv = x - 1; xv <= x; xv++) {
			for(int yv = y - 1; yv <= y; yv++) {
				if(map[xv][yv] == col) {
					continue;
				}
				if(xv == x - 1) {
					if(xv - 1 >= 0 && map[xv - 1][yv] == col) {
						if(addRes(xv, yv, UP)) {
							return;
						}
						continue;
					}
				} else {
					if(xv + 1 < height && map[xv + 1][yv] == col) {
						if(addRes(xv, yv, DOWN)) {
							return;
						}
						continue;
					}
				}
				if(yv == y - 1) {
					if(yv - 1 >= 0 && map[xv][yv - 1] == col) {
						if(addRes(xv, yv, LEFT)) {
							return;
						}
						continue;
					}
				} else {
					if(yv + 1 < width && map[xv][yv + 1] == col) {
						if(addRes(xv, yv, RIGHT)) {
							return;
						}
						continue;
					}
				}
				boolean found = false;
				for(int dist = 2; dist < MAX_POW && !found; dist++) {
					for(int k = Math.max(0, xv - dist); k <= Math.min(xv + dist, height - 1); k++) {
						int yk = dist - Math.abs(k - xv);
						if(yv - yk >= 0 && ((k != x - 1 && k != x) || yv - yk != y - 1) && map[k][yv - yk] == col) {
							found = true;
							int yvk = yv - yk;
							if(xv == x && k < xv && map[xv - 1][yv] == col) {
								addRes(xv, yv, UP);
								xv--;
							}
							if(xv == x - 1 && k > xv && map[xv + 1][yv] == col) {
								addRes(xv, yv, DOWN);
								xv++;
							}
							if(yv == y && yvk < yv && map[xv][yv - 1] == col) {
								addRes(xv, yv, LEFT);
								yv--;
							}
							if(yv == y - 1 && yvk > yv && map[xv][yv + 1] == col) {
								addRes(xv, yv, RIGHT);
								yv++;
							}
							if(moveCells(xv, yv, k, yvk)) {
								return;
							}
							break;
						}
						if(yv + yk < width && ((k != x - 1 && k != x) || yv + yk != y) && map[k][yv + yk] == col) {
							found = true;
							int yvk = yv + yk;
							if(xv == x && k < xv && map[xv - 1][yv] == col) {
								addRes(xv, yv, UP);
								xv--;
							}
							if(xv == x - 1 && k > xv && map[xv + 1][yv] == col) {
								addRes(xv, yv, DOWN);
								xv++;
							}
							if(yv == y && yvk < yv && map[xv][yv - 1] == col) {
								addRes(xv, yv, LEFT);
								yv--;
							}
							if(yv == y - 1 && yvk > yv && map[xv][yv + 1] == col) {
								addRes(xv, yv, RIGHT);
								yv++;
							}
							if(moveCells(xv, yv, k, yvk)) {
								return;
							}
							break;
						}
					}
				}
			}
		}
	}

	boolean moveCells(int x1, int y1, int x2, int y2) {
		while(x2 < x1) {
			if(map[x2 + 1][y2] == map[x2][y2]) {
				x2++;
				continue;
			}
			if(addRes(x2, y2, DOWN)) {
				return true;
			}
			x2++;
		}
		while(x2 > x1) {
			if(map[x2 - 1][y2] == map[x2][y2]) {
				x2--;
				continue;
			}
			if(addRes(x2, y2, UP)) {
				return true;
			}
			x2--;
		}
		while(y2 < y1) {
			if(map[x2][y2 + 1] == map[x2][y2]) {
				y2++;
				continue;
			}
			if(addRes(x2, y2, RIGHT)) {
				return true;
			}
			y2++;
		}
		while(y2 > y1) {
			if(map[x2][y2 - 1] == map[x2][y2]) {
				y2--;
				continue;
			}
			if(addRes(x2, y2, LEFT)) {
				return true;
			}
			y2--;
		}

		return false;
	}

	int getPower(int x, int y) {
		int power = MAX_POW * 2, bestCol = 0;
		int[] xs = new int[] {x - 1, x - 1, x, x}, ys = new int[] {y - 1, y, y - 1, y};
		for(int i = 0; i < xs.length - 1; i++) {
			for(int j = i + 1; j < xs.length; j++) {
				if(map[xs[i]][ys[i]] == map[xs[j]][ys[j]]) {
					int cx = i > 0 ? xs[0] : j > 1 ? xs[1] : xs[2];
					int cy = i > 0 ? ys[0] : j > 1 ? ys[1] : ys[2];
					int lx = 4 * x - 2 - xs[i] - xs[j] - cx;
					int ly = 4 * y - 2 - ys[i] - ys[j] - cy;
					int d1 = getMinDist(cx, cy, map[xs[i]][ys[i]], new int[] {xs[i], xs[j], lx}, new int[] {ys[i], ys[j], ly});
					if(d1 >= 0) {
						int nx = ((d1 & 255) >> 4), ny = (d1 & 15);
						int d2 = getMinDist(lx, ly, map[xs[i]][ys[i]], new int[] {xs[i], xs[j], nx}, new int[] {ys[i], ys[j], ny});
						if(d2 >= 0) {
							int np = (d1 >> 8) + (d2 >> 8);
							if(np < power) {
								power = np;
								bestCol = map[xs[i]][ys[i]];
							}
						}
					}
				}
			}
		}
		return (2 * MAX_POW - power) * nrColors + bestCol;
	}

	int getMinDist(int x, int y, int col, int[] excludedXs, int[] excludedYs) {
		if(map[x][y] == col) {
			return getBits(x, y);
		}
		for(int dist = 1; dist < MAX_POW; dist++) {
			for(int k = Math.max(0, x - dist); k <= Math.min(x + dist, height - 1); k++) {
				int yk = dist - Math.abs(k - x);
				if(y - yk >= 0 && map[k][y - yk] == col && !isIncluded(excludedXs, excludedYs, k, y - yk)) {
					return ((dist << 4) | getBits(k, y - yk));
				}
				if(y + yk < width && map[k][y + yk] == col && !isIncluded(excludedXs, excludedYs, k, y + yk)) {
					return ((dist << 8) | getBits(k, y + yk));
				}
			}
		}
		return -1;
	}
	
	boolean isIncluded(int[] xs, int[]ys, int x, int y) {
		for(int i = 0; i < ys.length; i++) {
	    if(xs[i] == x && ys[i] == y) {
	    	return true;
	    }
    }
		return false;
	}
	
	int getPw(int x, int y, int col) {
		int res = 0;
		for(int xv = x - 1; xv <= x; xv++) {
			for(int yv = y - 1; yv <= y; yv++) {
				if(map[xv][yv] == col) {
					continue;
				}
				// check dist 1
				if(xv == x - 1) {
					if(xv - 1 >= 0 && map[xv - 1][yv] == col) {
						res++;
						continue;
					}
				} else {
					if(xv + 1 < height && map[xv + 1][yv] == col) {
						res++;
						continue;
					}
				}
				if(yv == y - 1) {
					if(yv - 1 >= 0 && map[xv][yv - 1] == col) {
						res++;
						continue;
					}
				} else {
					if(yv + 1 < width && map[xv][yv + 1] == col) {
						res++;
						continue;
					}
				}
				// check dist 2 - MAX_POW
				boolean found = false;
				for(int dist = 2; dist < MAX_POW - res && !found; dist++) {
					for(int k = Math.max(0, xv - dist); k <= Math.min(xv + dist, height - 1); k++) {
						int yk = dist - Math.abs(k - xv);
						if(yv - yk >= 0 && ((k != x - 1 && k != x) || yv - yk != y - 1) && map[k][yv - yk] == col) {
							found = true;
							res += dist;
							break;
						}
						if(yv + yk < width && ((k != x - 1 && k != x) || yv + yk != y) && map[k][yv + yk] == col) {
							found = true;
							res += dist;
							break;
						}
					}
				}
				if(!found) {
					return MAX_POW;
				}
			}
		}
		return res;
	}

	boolean isIn(int x, int y) {
		return x >= 0 && x < height && y >= 0 && y < width;
	}

	void init(int colors, String[] board, int startSeed) {
		this.nrColors = colors;
		this.height = board.length;
		this.width = board[0].length();

		map = new int[height][width];
		for(int i = 0; i < map.length; i++) {
			for(int j = 0; j < map[i].length; j++) {
				map[i][j] = board[i].charAt(j) - '0';
			}
		}

		genColors(startSeed, colors);

		for(int i = 1; i < map.length; i++) {
			for(int j = 1; j < map[i].length; j++) {
				toCheckList.add(getBits(i, j));
			}
		}
		checkSq();
	}

	boolean addRes(int x, int y, int dir) {
		if(cInd == cres.length) {
			return true;
		}

		cres[cInd] = x;
		cres[cInd + 1] = y;
		cres[cInd + 2] = dir;
		cInd += 3;

		int nx = x + dx[dir];
		int ny = y + dy[dir];

		int tmp = map[x][y];
		map[x][y] = map[nx][ny];
		map[nx][ny] = tmp;

		if(x != nx) {
			int mx = Math.min(x, nx);
			toCheckList.add((mx << 4) | y);
			if(y + 1 < width) {
				toCheckList.add((mx << 4) | (y + 1));
			}
			if(mx + 2 < height) {
				toCheckList.add(((mx + 2) << 4) | y);
				if(y + 1 < width) {
					toCheckList.add(((mx + 2) << 4) | (y + 1));
				}
			}
		} else {
			int my = Math.min(y, ny);
			toCheckList.add((x << 4) | my);
			if(my + 2 < width) {
				toCheckList.add((x << 4) | (my + 2));
			}
			if(x + 1 < height) {
				toCheckList.add(((x + 1) << 4) | my);
				if(my + 2 < width) {
					toCheckList.add(((x + 1) << 4) | (my + 2));
				}
			}
		}
		return checkSq();
	}

	/** return ((x << 4) | y) */
	int getBits(int x, int y) {
		return ((x << 4) | y);
	}

	boolean checkSq() {
		boolean res = false;

		while(toCheckList.first != null) {
			int val = toCheckList.removeFirst();
			int x = (val >> 4), y = (val & 15);

			if(y > 0 && x > 0 && map[x][y] == map[x - 1][y - 1] && map[x][y] == map[x - 1][y] && map[x][y] == map[x][y - 1]) {
				res = true;
				cScore++;

				map[x - 1][y - 1] = colorVals[colInd];
				map[x - 1][y] = colorVals[colInd + 1];
				map[x][y - 1] = colorVals[colInd + 2];
				map[x][y] = colorVals[colInd + 3];
				colInd += 4;

				toCheckList.addSorted(getBits(x - 1, y - 1));
				toCheckList.addSorted(getBits(x - 1, y));
				if(y + 1 < width) {
					toCheckList.addSorted(getBits(x - 1, y + 1));
				}
				toCheckList.addSorted(getBits(x, y - 1));
				toCheckList.addSorted(getBits(x, y));
				if(y + 1 < width) {
					toCheckList.addSorted(getBits(x, y + 1));
				}
				if(x + 1 < height) {
					toCheckList.addSorted(getBits(x + 1, y - 1));
					toCheckList.addSorted(getBits(x + 1, y));
					if(y + 1 < width) {
						toCheckList.addSorted(getBits(x + 1, y + 1));
					}
				}
			}
		}

		return res;
	}

	void genColors(int seed, int colors) {
		int cur = seed;
		colorVals[0] = cur % colors;
		for(int i = 1; i < colorVals.length; i++) {
			cur = (int) (((long) cur * MUL) % MOD);
			colorVals[i] = cur % colors;
		}
	}

	int[][] mapCopy() {
		int[][] mapRes = new int[height][width];
		for(int i = 0; i < mapRes.length; i++) {
			System.arraycopy(map[i], 0, mapRes[i], 0, width);
		}
		return mapRes;
	}
}

class MyLinkedList {
	MyLinkedNode first = null, last = null;

	void add(int val) {
		if(first == null) {
			first = last = new MyLinkedNode(val);
		} else {
			last.next = new MyLinkedNode(val);
			last = last.next;
		}
	}

	int removeFirst() {
		int res = first.val;
		first = first.next;
		return res;
	}

	void addSorted(int val) {
		if(first == null) {
			first = last = new MyLinkedNode(val);
		} else if(first.val > val) {
			MyLinkedNode newFirst = new MyLinkedNode(val);
			newFirst.next = first;
			first = newFirst;
		} else {
			MyLinkedNode c = first;
			while(c.next != null && c.next.val < val) {
				c = c.next;
			}
			if(c.next == null) {
				last.next = new MyLinkedNode(val);
				last = last.next;
			} else if(c.next.val > val) {
				MyLinkedNode newNode = new MyLinkedNode(val);
				newNode.next = c.next;
				c.next = newNode;
			}
		}
	}
}

class MyLinkedNode {
	int val;
	MyLinkedNode next = null;

	public MyLinkedNode(int val) {
		this.val = val;
	}
}

class State {
	int step = 0;
	int[][] cMap = null;
	int genStep = 0;
	int score = 0;
	int[] sRes = null;
}

